382C - Arithmetic Progression - CodeForces Solution

#include <iomanip>
#include <iostream>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <numeric>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<int, int> mii;
typedef map<char, int> mci;
 
#define f first
#define s second
#define mp make_pair
 
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) x.size()
 
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 1e7;

void solve() {
    int n; cin >> n;
    vll a(n);
    for (int i = 0; i < n; i++) 
        cin >> a[i];

    set<int> ans;
    sort(all(a));
    if (n == 1) {
        cout << -1 << '\n';
        return;
    } else if (n == 2) {
        ll d = a[1] - a[0];
        if (d % 2 == 0) {
            ans.insert(a[0] + d/2);
        }
        ans.insert(a[0] - d);
        ans.insert(a[1] + d);
    } else {
        map<ll, vll> diff;
        for (int i = 0; i < n-1; i++) {
            ll d = a[i+1] - a[i];
            diff[d].pb(a[i] + d/2);
        }

        if (diff.size() == 1) {
            ll d = diff.begin()->f;
            ans.insert(a[0] - d);
            ans.insert(a[n-1] + d);
        } else if (diff.size() == 2) {
            auto x = diff.begin();
            auto y = ++diff.begin();
            if (x->s.size() == 1 && x->f % 2 == 0 && x->f/2 == y->f) {
                ans.insert(x->s.front());
            } else if (y->s.size() == 1 && y->f % 2 == 0 && y->f/2 == x->f) {
                ans.insert(y->s.front());
            }
        }
    }

    cout << ans.size() << '\n';
    for (auto x : ans) {
        cout << x << ' ';
    }
    cout << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    // int t; cin >> t;
    // while (t--)
    //     solve();
	solve(); 
	return 0;
}